package leetcode_周赛._2023._02;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 第 332 场周赛
 * AC_1
 *
 * @author yezh
 * @date 2023/2/12 16:36
 */
public class _12 {

    /**
     * 找出数组的串联值
     * 算法：模拟
     */
    public long findTheArrayConcVal(int[] nums) {
        long ans = 0;
        int n = nums.length;
        for (int i = 0; i < n / 2; i++) {
            int a = nums[i], b = nums[n - i - 1];
            while (b != 0) {
                a *= 10;
                b /= 10;
            }
            ans += a + nums[n - i - 1];
        }
        if (n % 2 != 0) ans += nums[n / 2];
        return ans;
    }

    /**
     * 统计公平数对的数目
     * 算法：二分
     * 做的时候想到二分了, 但是被 i < j 这个条件限制了,
     * 实际上根本不需要考虑这个条件, 直接排序即可, 只要保证数对不重复
     * lower <= nums[i] + nums[j] <= upper
     * lower - nums[j] <= nums[i] <= upper - nums[j]
     */
    public long countFairPairs(int[] nums, int lower, int upper) {
        long ans = 0;
        Arrays.sort(nums);
        for (int j = 0; j < nums.length; j++) {
            int l = lower - nums[j], r = upper - nums[j];
            ans = binarySearch(nums, j - 1, r + 1) - binarySearch(nums, j - 1, l);
        }
        return ans;
    }

    int binarySearch(int[] nums, int r, int target) {
        int l = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (nums[mid] < target) l = mid + 1;
            else r = mid - 1;
        }
        return l;
    }

    /**
     * 子字符串异或查询
     * 算法：哈希表 + 位运算
     * val ^ first = second ==> val = second ^ first
     * 0 <= firsti, secondi <= 10 ^ 9, int 最大为 2 ^ 31 - 1
     * 所以, 二进制字符串最长为 31
     */
    public int[][] substringXorQueries(String s, int[][] queries) {
        int[][] ans = new int[queries.length][2];
        int len = s.length();
        Map<Integer, int[]> map = new HashMap<>();
        int[] notFount = new int[]{-1, -1};
        for (int i = 0; i < len; i++) {
            int val = 0;
            for (int j = i; j < Math.min(i + 30, len); j++) {
                val = (val << 1) | (s.charAt(j) - '0');
                int[] tmp = map.getOrDefault(val, notFount);
                if (tmp[0] == -1 || j - i < tmp[1] - tmp[0]) map.put(val, new int[]{i, j});
            }
        }
        for (int i = 0; i < queries.length; i++) ans[i] = map.getOrDefault(queries[i][0] ^ queries[i][1], notFount);
        return ans;
    }

}
